In 2000, Zellweger (U.S. Pat. No. 6,131,098) introduced a novel way to navigate over database content using a content menu. This end-user interface organizes data and data relations found in the database according to the open hierarchical data structure (OHDS), a list of nested lists, first described by Zellweger (U.S. Pat. No. 5,630,125) in 1997. The OHDS is similar to the “[LEFT child—RIGHT sibling]” data structure described by Knuth, but Zellweger's implementation of this structure goes well beyond the simple functionality of memory management tool. Having its own interactive development system and a comprehensive set of tools for managing data-topic lists, menu developers can add menu topics either by hand, by algorithms that extract data and data relations from a database, or by combinations of both.
Over the past decade, the construction of the OHDS served as a framework for improving the algorithms that automate menu data for the content menu. The data mapping algorithm used to build the OHDS is recursive. Each recursive call extracts a list of data-topics from a remote database and adds it to a leaf node in the OHDS. By systematically branching out from each leaf node at the bottom of the structure, this technique is similar to the tree-growing methodology described by Biggs which mimic the depth-first search. By carefully observing these operations, the OHDS provided an opportunity for seeing how runtime data-topic lists could be added to the content menu, along with numerous other improvements, including U.S. Pat. Nos. 6,234,700 and 6,301,583.
Early on Zellweger was able to show how to automatically generate a network of data-topic lists for the OHDS. This included using a dedicated interactive menu (U.S. Pat. No. 6,131,100) and specialized software (U.S. Pat. No. 6,279,005). In U.S. Pat. No. 6,131,100, a newly disclosed GUI enables the menu developer to navigate over a target database and to create a series of “logical” relationships between a pair of database attributes. In turn, these logical relationships could be represented by a symbolic expression. Program logic disclosed by U.S. Pat. No. 6,279,005 shows how to parse this expression to capture meta-query data. This data is used to construct a query statement at runtime that extracts lists of data-topics from a remote, target database. Improvements to these advances include U.S. Pat. No. 6,131,098 that parses this symbolic expression to extract meta-query data and stores it in its own structure. These new improvements enable the same meta-query data to generate a OHDS for compiled menu data files or for creating menu data for the content menu at runtime.
The current disclosure introduces a number of new improvements over all of this prior art. These improvements are all essentially based an entirely new perspective on meta-query data. This new perspective on meta-query data was inspired by Burgin's mathematical theory of named sets. This advanced mathematical theory was instrumental in the development of binary attribute relations (BAR) and in shaping the details for a new model of meta-query data. This new format is presented in this disclosure. At the core of this new disclosure is the discovery of a uniform pattern of data relations in all database applications that can be represented by a new meta-query query model. This uniform pattern of data relations is identified here as binary attribute data relations, and they will be described shortly.
At this point in this disclosure, it is important to point out how two other discoveries relate to these data relations, and to each other. These two discoveries are: 1) a simplified retrieval operation called a BAR query that extracts data relations according to meta-query data, and 2) the fact that these data relations can be classified according to how they contribute to the construction of the OHDS. Therefore, these two additional discoveries are, in fact, so closely intertwined with each other that one discovery could not be made independent of the other. The BAR query, a simplified retrieval operation, lends itself to the construction of the OHDS; and the OHDS in turn reveals the nature of data relations in the database and how they can be enumerated and classified according to four distinct types.
Clearly, these four different types of data relations occur routinely in everyday programming, and they could be extracted from a database using less efficient algorithms. But they could never have been discovered, let alone classified in such a systematic or unified manner, without the BAR query, and without the knowledge of their role in the construction of the OHDS.
As indicated earlier, the BAR and the BAR query are applications of Burgin's theory of named sets (BNS), a mathematical modeling tool more fundamental than set theory, the dominant mathematics behind the relational data model. BNS assumes that all systems are composed of interrelated components or subsystems that are logically related by “rules.” In the case of the relational database, these components include a pair of attributes in a relational table and the rules imposed by a simple SQL SELECT that bind the two attributes together.
It is important to note that the binary attribute data relations introduced by this disclosure occur naturally between two attributes in every database table. As indicated above, they could only be derived from a well-defined, carefully crafted retrieval operation like the BAR query. The inventor discovered the logical relationship established by the BAR query as a data relation between an input data condition and its data. He calls this relationship a binary attribute data relations or BADRs.
With these new understanding in place, this disclosure is now in a better position to identify four different types of data relations that exist in all database applications. Before proceeding to the disclosure itself, however, it is important to point out why these data relations have remained hidden from view. One reason for their obscurity is that the BAR query is essentially a new tool, one that until now has never been considered. Another reason for their obscurity is that the data mapping between an input condition and its data output is entirely deterministic, the actual number of data in the output is completely unpredictable and arbitrary.
For example, in a BAR query with an input condition COLOR=red, the retrieval operation logically binds a single data value red with the COLOR attribute. In a database table, however, there may be multiple instances of red at various record, row or tuple locations. Yet, the BAR query statement treats all these matching values mathematically as an instance of one, according set theory. In contrast, data output from this query can be one or many depending upon the number of red locations in the table, and on the number of unique data values associated with the output attribute. This means that the data mapping between input and output attributes can take the form of “one-to-one” or “one-to-many,” regardless of the database table declaration or the samples of data considered. Therefore, arbitrary nature of these data relations makes them difficult to “see” and to “identify,” particularly through the lens of set theory because it has no way of modeling them.
But from the perspective of the content menu, this output data plays an essential role in construction of the OHDS regardless of whether they take the form of “one-to-one” or “one-to-many.” What also makes a difference is whether the output from a BAR query data represents data-topics that would be relevant or meaningful to an end-user. This raises another important point, namely that some of this output data only serves as links to data-topics, representing two of the four different types of binary attribute data relations. Therefore, without the OHDS, the difference between these four different types of data relations could not have been made.
A careful analysis of the construction of the OHDS and of the BAR query afforded other discoveries as well, including a more precise understanding of the nature of relational data. In particular, this understanding includes the notion that all relational data is composed of two system-based aspects: physical-values and constructed-types. The inventor identifies these two aspects of this data as meta-symbols that represent the mechanical way the database processes input and output data. The input condition on an input attribute relies on “pattern matching” 0's and 1's to locate relevant records in the database. Operationally, this matching occurs in the Arithmetic logic unit of ALU of the computer's CPU by comparing an input text condition with record components. In contrast, the output attribute focuses on the “naming” function of an attribute label that refers to pools of data symbols in a database table. Therefore, the inventor views all input services as being based on the physical-value of data-symbols and all output as being based on constructed objects that manage them. With this deeper understanding of relational data brought about by the awareness of a division of labor between input and output, all retrieval operations on structured data can now be generalized across all different types of regardless of any data model.
Therefore, all retrieval operations, including relational queries such as the SQL SELECT, can and should be viewed as an input/output interface to an algorithm. The input and output channels themselves align with the phenomenon of meta-symbols: with physical data values used to match input patterns, and with constructed-types, such as attributes, for extracting data from a pool of values by an attribute name. At the data level, differentiating input and output data by how the database functions internally gives shape and form to the BADR discovered by the inventor. First, by showing how each one contributes to the construction of the OHDS. Output provides sibling lists and input physical-values furnishes the means for linking these lists to leaf nodes in this structure. Next, by characterizing these two attributes as a source and destination, this new logical relationship draws attention to the mapping between such input and output data.
In the database literature, the inventor's input and output view of retrieval operations is somewhat consistent with the more general concept of query mapping that refers to input and output schema mapping (Abiteboul et al.). However, in the inventor's case, this mapping is quite specific as it refers to input and output data. This takes us well beyond today's theoretical understanding of database queries, relational data, and even the notion of physical symbols according to Simon and Newell, as all of these various concepts have never been studied together from the perspective of data relations.
These two refinements (all queries simply refer to input and output and the fact that this i/o can easily be modeled by the BAR symbolic expression) help clarify and articulate data relations in the relational database. Until now, this area has been unexplored by the database research community. By focusing on the mapping between input data and data output from a BAR query, and the fact that this data relationship can be arbitrarily either one or many, these data relations could only emerge and unfold when the OHDS and its construction was taken into consideration. Therefore, this data mapping could only exist within the carefully constructed framework of a BAR query and of an OHDS, making the discovery of this data mapping the subject for this new art, with the BAR query the predicate and the content menu its object.
The discovery of binary attribute data relations or BADRs provides an entirely fresh, new look at the data and data relations in a database. This new perspective lays the foundation for a more tightly integrated approach toward generating menu data for the content menu. By design, this new approach improves upon the prior techniques in a number of significant ways. First, with the BAR query as a focal point for extracting menu data from a database, the algorithms that populate the OHDS can be more streamlined and compact. They are also considerably easier to maintain. Second, now that the nature of relational data is better understood. and more precise in terms of retrieval operations, improvements could be made to the format of meta-query data and to the way it is collected and stored. Third, by separating the BAR query from the algorithms that build the OHDS, this simple query could now generate menu data for runtime list menus as well.
Finally, with the discovery of binary attribute data relations, the inventor was able to identify the rules that govern attribute and data relations. By analyzing these rules, new insights about the nature of data relations can be made. One such insight that can be attributed to this discovery is that the semantic relations in the newly discovered data relations that fall into two broad categories: contextual information and conceptual linkage. Another important insight focuses on how different pairs of attributes can create different types of data relations that contribute to the construction of the OHDS.
What makes this disclosure so exceptional is the fact that the binary attribute relation or BAR challenges a longstanding position in the research literature. In 1978, Codd, the inventor of the relational database, argued against extending any semantic analysis within a relational table at the attribute level. The reason for his strongly worded position is that he considered the relational table to be semantically “atomic” p. 413. At best, he was ambivalent about even considering something like the binary attribute relations because he did not see any point to such speculation. Since then, however, no one has been able to show how attributes within the same table could form any relevant semantic relationships that would challenge Codd's. Database researchers have not even considered the possibility that a semantic relationship could exist between two attributes. Nor had they considered that any two attributes in a relational table could form a logical relationship that could express the underlying relationship of their data. Fortunately, however, these two topics are taken up by the present disclosure in a concrete and pragmatic way with the content menu.
Therefore, this disclosure breaks new ground by providing hard evidence, from the perspective of the content menu, that BADRs are both useful and meaningful. At the data level, the BAR query yields BADRs which provide the essential building blocks for constructing a database taxonomy. At the attribute or naming level, the input and output functions of the BAR query frame the terms in the BAR notation in a new light. That is, the input and output attributes in a BAR query can be applied directly to the formation of a BAR expression. Furthermore, the attribute, and its underlying data, can also now be viewed as a resource that can either describe something about the content in a database, say when the attribute SIZE manages data such as small or medium. Or that these resources can be employed as links to such descriptions for end-users. This new distinction between attribute data describing versus linking provides the means to classify attributes—and their data—operationally as either conceptual or operational, according to how an attribute, in a sequence of attributes selected by a developer, contributes to the construction of the content menu.
This classification of attributes and their data as being either conceptual or operational is essential in showing how binary attribute data relations or BADR characterize semantic relations. When data-symbols from two conceptual attributes both describe something, such as “Boston” and “Massachusetts,” they establish a particular type of semantic relationship that is identified here as contextual information. Together these two data-symbols not only describe something modeled by the database table, they also provide a contextual setting that clarifies each term. Case in point, they refer to a specific town in a particular state. Other semantic relations are also possible. For instance, when a data-symbol from an operational attribute links to another data-symbol (a description or another link) that establishes another type of semantic relationship that is identified here as conceptual linkage. This other type of relationship eventually links to conceptual information. In the construction of the OHD, all operational data is stripped away in order to display only data-symbols that will inform end-users about what they can expect to find in the database. Thus, one can see how these two semantic expressions are functionally related, and how the concepts of the BAR query and the BADR are mutually dependent upon each other, in a complementary way, for the discovery of their respective identities.